template <typename T, class VST>
void travPre_R(BinNodePosi(T) x, VST &visit) {
	if(!x) return;

	visit(x->data);
	travPre_R(x->lc, visit);
	travPre_R(x->rc, visit);
}

template <typename T, class VST>
static void visitAlongLeftBranch(BinNodePosi(T) x, VST &visit, std::stack<BinNodePosi(T)> &s) {
	while(x) {
		visit(x->data);
		s.push(x->rc);
		x = x->lc;
	}
}

template<class T, typename VST>
void travPre_I1(BinNodePosi(T) x, VST &visit) {
	if(!x) return;
	std::stack<BinNodePosi(T)> s;
	s.push(x);
	while(!s.empty()) {
		BinNodePosi(T) cur = s.top();
		s.pop();

		if(!cur) continue;
		visit(cur->data);

		s.push(cur->rc);
		s.push(cur->lc);
	}
}
template<class T, typename VST>
void travPre_I2(BinNodePosi(T) x, VST &visit) {
	std::stack<BinNodePosi(T)> s;
	while(true) {
		visitAlongLeftBranch(x, visit, s);
		if(s.empty()) break;

		x = s.top();
		s.pop();
	}
}